
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1665. -- [Usaco2006 Open]The Climbing Wall -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1665: [Usaco2006 Open]The Climbing Wall</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>108&nbsp;&nbsp;<span class=green>Solved: </span>39<br>[<a href='submitpage.php?id=1665'>Submit</a>][<a href='problemstatus.php?id=1665'>Status</a>][<a href='bbs.php?id=1665'>Discuss</a>]</center><h2>Description</h2><div class=content>One of the most popular attractions at the county fair is the
climbing wall. Bessie wants to plan her trip up the wall in advance
and needs your help.

The wall is 30,000 millimeters wide and H (1001 <= H <= 30,000)
millimeters high and has F (1 <= F <= 10,000) hoof-holds at unique
X,Y coordinates expressed in millimeters. 0,0 is at the ground level
on the left side of the wall. Hoof-holds are separated by at least
300 millimeters since no cow can maneuver them if they are spaced
too close! Bessie knows there is at least one way up.

Bessie, through techniques only she knows, uses successive single
hoof-holds to climb the wall. She can only move from one hoof-hold
to another if they are no more than one meter apart. She can, of
course, move up, down, right, left or some combination of these in
each move. Similarly, once she gets to a hoof-hold that is at least
H-1000 millimeters above the ground, she can nimbly climb from there
onto the platform atop the wall. Bessie can start at any X location
that has a Y location <= 1000 millimeters.

Given the height of the wall and the locations of the hoof-holds,
determine the smallest number of hoof-holds Bessie should use to
reach the top.

Bessie参加了爬墙比赛，比赛用的墙宽30000,高H(1001 <= H <= 30,000)。墙上有F(1 <= F <= 10,000)个不同的落脚点（X，Y）。 （0，0）在左下角的地面。所有的落脚点至少相距300。Bessie知道至少有一条路可以上去。
Bessie只能从一个落脚点爬到另一个距离不超过1000的落脚点，她可以向上下左右四个方向爬行。同样地，一旦她到达了一个高度 至少有H-1000的落脚点，她可以敏捷地爬到墙顶上。Bessie一开始可以在任意一个高度不超过1000的落脚点上。
问Bessie至少攀爬多少次.这里两个点的距离都是欧几里得距离</div><h2>Input</h2><div class=content>* Line 1: Two space-separated integers, H and F.

* Lines 2..F+1: Each line contains two space-separated integers
        (respectively X and Y) that describe a hoof-hold. X is the
        distance from the left edge of the climbing wall; Y is the
        distance from the ground.

</div><h2>Output</h2><div class=content>* Line 1: A single integer that is the smallest number of hoof-holds
        Bessie must use to reach the top of the climbing wall.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3000 5<br />
600 800<br />
1600 1800<br />
100 1300<br />
300 2100<br />
1600 2300<br />
<br />
INPUT DETAILS:<br />
<br />
The wall is three meters high with 5 hoof-holds.<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>3<br />
<br />
OUTPUT DETAILS:<br />
<br />
Bessie can start on the ground, move to the hoof-hold at (600,800), move<br />
from there to (100,1300), move from there to (300,2100), and from that high<br />
height can hop onto the platform. This trip requires three hoof-holds. <br />
There is no shorter path that Bessie can take.</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver
'>Silver<br />
</a></p></div><center>[<a href='submitpage.php?id=1665'>Submit</a>][<a href='problemstatus.php?id=1665'>Status</a>][<a href='bbs.php?id=1665'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
